__author__ = 'gschwartzbard'

import unittest
from radix_tree import RadixTree, DuplicateKeyError

class MyTestCase(unittest.TestCase):
    def setUp(self):
        self.trie = RadixTree()

    def test_search_for_partial_parent_and_leaf_key_when_overlap_exists(self):
        self.trie.insert("abcd", "abcd")
        self.trie.insert("abce", "abce")

        self.assertEqual(0, len(self.trie.search_prefix("abe", 10)))
        self.assertEqual(0, len(self.trie.search_prefix("abd", 10)))

    def test_search_for_leaf_nodes_when_overlap_exists(self):
        self.trie.insert("abcd", "abcd")
        self.trie.insert("abce", "abce")

        self.assertEqual(1, len(self.trie.search_prefix("abcd", 10)))
        self.assertEqual(1, len(self.trie.search_prefix("abce", 10)))

    def test_search_for_string_smaller_than_shared_parent_when_overlap_exists(self):
        self.trie.insert("abcd", "abcd")
        self.trie.insert("abce", "abce")

        self.assertEqual(2, len(self.trie.search_prefix("ab", 10)))
        self.assertEqual(2, len(self.trie.search_prefix("a", 10)))

    def test_search_for_string_equal_to_shared_parent_when_overlap_exists(self):
        self.trie.insert("abcd", "abcd")
        self.trie.insert("abce", "abce")

        self.assertEqual(2, len(self.trie.search_prefix("abc", 10)))

    def test_insert(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("bat", "bat")
        self.trie.insert("ape", "ape")
        self.trie.insert("bath", "bath")
        self.trie.insert("banana", "banana")

        self.assertEqual(self.trie.find("apple"), "apple")
        self.assertEqual(self.trie.find("bat"), "bat")
        self.assertEqual(self.trie.find("ape"), "ape")
        self.assertEqual(self.trie.find("bath"), "bath")
        self.assertEqual(self.trie.find("banana"), "banana")

    def test_insert_existing_unreal_node_converts_it_to_real(self):
        self.trie.insert("applepie", "applepie")
        self.trie.insert("applecrisp", "applecrisp")

        self.assertFalse(self.trie.contains("apple"))

        self.trie.insert("apple", "apple")

        self.assertTrue(self.trie.contains("apple"))

    def test_duplicates_not_allowed(self):
        self.trie.insert("apple", "apple")
        self.assertRaises(DuplicateKeyError, self.trie.insert, "apple", "apple")

    def test_insert_with_repeating_patterns_in_key(self):
        self.trie.insert("xbox 360", "xbox 360")
        self.trie.insert("xbox", "xbox")
        self.trie.insert("xbox 360 games", "xbox 360 games")
        self.trie.insert("xbox games", "xbox games")
        self.trie.insert("xbox xbox 360", "xbox xbox 360")
        self.trie.insert("xbox xbox", "xbox xbox")
        self.trie.insert("xbox 360 xbox games", "xbox 360 xbox games")
        self.trie.insert("xbox games 360", "xbox games 360")
        self.trie.insert("xbox 360 360", "xbox 360 360")
        self.trie.insert("xbox 360 xbox 360", "xbox 360 xbox 360")
        self.trie.insert("360 xbox games 360", "360 xbox games 360")
        self.trie.insert("xbox xbox 361", "xbox xbox 361")

        self.assertEqual(12, self.trie.size)

    def test_delete_node_with_no_children(self):
        self.trie.insert("apple", "apple")
        self.assertTrue(self.trie.delete("apple"))

    def test_delete_node_with_one_child(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("applepie", "applepie")

        self.assertTrue(self.trie.delete("apple"))
        self.assertTrue(self.trie.contains("applepie"))
        self.assertFalse(self.trie.contains("apple"))

    def test_delete_node_with_multiple_children(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("applepie", "applepie")
        self.trie.insert("applecrisp", "applecrisp")

        self.assertTrue(self.trie.delete("apple"))
        self.assertTrue(self.trie.contains("applepie"))
        self.assertTrue(self.trie.contains("applecrisp"))
        self.assertFalse(self.trie.contains("apple"))

    def test_cant_delete_something_that_doesnt_exist(self):
        self.assertFalse(self.trie.delete("apple"))

    def test_cant_delete_something_that_was_already_deleted(self):
        self.trie.insert("apple", "apple")
        self.trie.delete("apple")
        self.assertFalse(self.trie.delete("apple"))

    def test_children_not_affected_when_one_is_deleted(self):
        self.trie.insert("apple", "apple");
        self.trie.insert("appleshack", "appleshack");
        self.trie.insert("applepie", "applepie");
        self.trie.insert("ape", "ape");

        self.trie.delete("apple");

        self.assertTrue(self.trie.contains("appleshack"))
        self.assertTrue(self.trie.contains("applepie"))
        self.assertTrue(self.trie.contains("ape"))
        self.assertFalse(self.trie.contains("apple"))

    def test_siblings_not_affected_when_one_is_deleted(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ball", "ball")

        self.trie.delete("apple")

        self.assertTrue(self.trie.contains("ball"))

    def test_cant_delete_unreal_node(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ape", "ape")

        self.assertFalse(self.trie.delete("ap"))

    def test_cant_find_root_node(self):
        self.assertFalse(self.trie.find(""))

    def test_find_simple_insert(self):
        self.trie.insert("apple", "apple")
        self.assertTrue(self.trie.find("apple"))

    def test_contains_simple_insert(self):
        self.trie.insert("apple", "apple")
        self.assertTrue(self.trie.contains("apple"))

    def test_find_child_insert(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ape", "ape")
        self.trie.insert("appletree", "appletree")
        self.trie.insert("appleshackcream", "appleshackcream")
        self.assertTrue(self.trie.find("appletree"))
        self.assertTrue(self.trie.find("appleshackcream"))
        self.assertTrue(self.trie.contains("ape"))

    def test_contains_child_insert(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ape", "ape")
        self.trie.insert("appletree", "appletree")
        self.trie.insert("appleshackcream", "appleshackcream")
        self.assertTrue(self.trie.contains("appletree"))
        self.assertTrue(self.trie.contains("appleshackcream"))
        self.assertTrue(self.trie.contains("ape"))

    def test_cant_find_nonexistant_node(self):
        self.assertFalse(self.trie.find("apple"))

    def test_doesnt_contain_nonexistant_node(self):
        self.assertFalse(self.trie.contains("apple"))

    def test_cant_find_unreal_node(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ape", "ape")
        self.assertFalse(self.trie.find("ap"))

    def test_doesnt_contain_unreal_node(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("ape", "ape")
        self.assertFalse(self.trie.contains("ap"))

    def test_search_prefix_limit_greater_than_possible_results(self):
        self.trie.insert("apple", "apple");
        self.trie.insert("appleshack", "appleshack");
        self.trie.insert("appleshackcream", "appleshackcream");
        self.trie.insert("applepie", "applepie");
        self.trie.insert("ape", "ape");

        result = self.trie.search_prefix("app", 10);
        self.assertEquals(4, len(result))

        self.assertTrue(result.index("appleshack") >= 0)
        self.assertTrue(result.index("appleshackcream") >= 0)
        self.assertTrue(result.index("applepie") >= 0)
        self.assertTrue(result.index("apple") >= 0)

    def test_search_prefix_limit_less_than_possible_results(self):
        self.trie.insert("apple", "apple");
        self.trie.insert("appleshack", "appleshack");
        self.trie.insert("appleshackcream", "appleshackcream");
        self.trie.insert("applepie", "applepie");
        self.trie.insert("ape", "ape");

        result = self.trie.search_prefix("appl", 3);
        self.assertEquals(3, len(result))

        self.assertTrue(result.index("appleshack") >= 0)
        self.assertTrue(result.index("applepie") >= 0)
        self.assertTrue(result.index("apple") >= 0)

    def test_get_size(self):
        self.trie.insert("apple", "apple");
        self.trie.insert("appleshack", "appleshack");
        self.trie.insert("appleshackcream", "appleshackcream");
        self.trie.insert("applepie", "applepie");
        self.trie.insert("ape", "ape");

        self.assertEqual(5, self.trie.size)

    def test_delete_reduces_size(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("appleshack", "appleshack")

        self.trie.delete("appleshack")

        self.assertEqual(1, self.trie.size)

    def test_complete(self):
        self.trie.insert("apple", "apple")
        self.trie.insert("appleshack", "appleshack")
        self.trie.insert("applepie", "applepie")
        self.trie.insert("applegold", "applegold")
        self.trie.insert("applegood", "applegood")

        self.assertEquals("", self.trie.complete("z"))
        self.assertEquals("apple", self.trie.complete("a"))
        self.assertEquals("apple", self.trie.complete("app"))
        self.assertEquals("appleshack", self.trie.complete("apples"))
        self.assertEquals("applego", self.trie.complete("appleg"))


if __name__ == '__main__':
    unittest.main()
